class Grid {
    x;
    y;
    f;
    g;
    h;
    parent;
    constructor(x, y) {
      this.x = x;
      this.y = y;
    }
    initGrid(parent, end) {
      this.parent = parent;
      this.g = parent.g + 1;
      this.h = Math.abs(this.x - end.x) + Math.abs(this.y - end.y);
      this.f = this.g + this.h;
    }
  }
  const MAZE = [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0]
  ];
  class AStar {
    /**
     * A星寻路主逻辑
     * @param start  迷宫起点
     * @param end  迷宫终点
     */
    static aStarSearch(start, end) {
      let openList = new Array();
      let closeList = new Array();
      //把起点加入 openList
      openList.push(start);
      //主循环，每一轮检查一个当前方格节点
      while (openList.length > 0) {
        // 在openList中查找 F值最小的节点作为当前方格节点
        let currentGrid = AStar.findMinGird(openList);
        // 当前方格节点从openList中移除
        let currentIndex = openList.findIndex(item => item.x === currentGrid.x && item.y === currentGrid.y);
        openList.splice(currentIndex, 1);
        // 当前方格节点进入 closeList
        closeList.push(currentGrid);
        // 找到所有邻近节点
        let neighbors = AStar.findNeighbors(currentGrid, openList, closeList);
        for (let grid of neighbors) {
          if (!openList.find(item => item.x === grid.x && item.y === grid.y)) {
            //邻近节点不在openList中，标记父亲、G、H、F，并放入openList
            grid.initGrid(currentGrid, end);
            openList.push(grid);
          }
        }
        //如果终点在openList中，直接返回终点格子
        for (let grid of openList) {
          if ((grid.x == end.x) && (grid.y == end.y)) {
            return grid;
          }
        }
      }
      //openList用尽，仍然找不到终点，说明终点不可到达，返回空
      return null;
    }
    static findMinGird(openList) {
      let tempGrid = openList[0];
      for (let grid of openList) {
        if (grid.f < tempGrid.f) {
          tempGrid = grid;
        }
      }
      return tempGrid;
    }
    static findNeighbors(grid, openList, closeList) {
      let gridList = new Array();
      if (AStar.isValidGrid(grid.x, grid.y - 1, openList, closeList)) {
        gridList.push(new Grid(grid.x, grid.y - 1));
      }
      if (AStar.isValidGrid(grid.x, grid.y + 1, openList, closeList)) {
        gridList.push(new Grid(grid.x, grid.y + 1));
      }
      if (AStar.isValidGrid(grid.x - 1, grid.y, openList, closeList)) {
        gridList.push(new Grid(grid.x - 1, grid.y));
      }
      if (AStar.isValidGrid(grid.x + 1, grid.y, openList, closeList)) {
        gridList.push(new Grid(grid.x + 1, grid.y));
      }
      return gridList;
    }
    static isValidGrid(x, y, openList, closeList) {
      //是否超过边界
      if (x < 0 || x >= MAZE.length || y < 0 || y >= MAZE[0].length) {
        return false;
      }
      //是否有障碍物
      if (MAZE[x][y] == 1) {
        return false;
      }
      //是否已经在openList中
      if (AStar.containGrid(openList, x, y)) {
        return false;
      }
      //是否已经在closeList中
      if (AStar.containGrid(closeList, x, y)) {
        return false;
      }
      return true;
    }
    static containGrid(grids, x, y) {
      for (let grid of grids) {
        if ((grid.x == x) && (grid.y == y)) {
          return true;
        }
      }
      return false;
    }
  }
  //设置起点和终点
  let startGrid = new Grid(2, 1);
  let endGrid = new Grid(2, 5);
  //搜索迷宫终点
  let resultGrid = AStar.aStarSearch(startGrid, endGrid);
  //回溯迷宫路径
  let path = new Array();
  while (resultGrid != null) {
    path.push(new Grid(resultGrid.x, resultGrid.y));
    resultGrid = resultGrid.parent;
  }
  let pathStr = '';
  //输出迷宫和路径，路径用星号表示
  for (let i = 0; i < MAZE.length; i++) {
    for (let j = 0; j < MAZE[0].length; j++) {
      if (AStar.containGrid(path, i, j)) {
        pathStr += "*, ";
      } else {
        pathStr += MAZE[i][j] + ", ";
      }
    }
    pathStr += '\n';
  }
  console.log(pathStr);
  /*
  0, 0, *, *, *, *, 0, 
  0, 0, *, 1, 0, *, 0, 
  0, *, *, 1, 0, *, 0, 
  0, 0, 0, 1, 0, 0, 0, 
  0, 0, 0, 0, 0, 0, 0, 
   */